{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 01 kNN 基础"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### kNN 基础概念\n",
    "\n",
    "见PPT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 实现我们自己的 kNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 创建简单测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "raw_data_X = [[3.393533211, 2.331273381],\n",
    "              [3.110073483, 1.781539638],\n",
    "              [1.343808831, 3.368360954],\n",
    "              [3.582294042, 4.679179110],\n",
    "              [2.280362439, 2.866990263],\n",
    "              [7.423436942, 4.696522875],\n",
    "              [5.745051997, 3.533989803],\n",
    "              [9.172168622, 2.511101045],\n",
    "              [7.792783481, 3.424088941],\n",
    "              [7.939820817, 0.791637231]\n",
    "             ]\n",
    "raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X_train = np.array(raw_data_X)\n",
    "y_train = np.array(raw_data_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 3.39353321,  2.33127338],\n",
       "       [ 3.11007348,  1.78153964],\n",
       "       [ 1.34380883,  3.36836095],\n",
       "       [ 3.58229404,  4.67917911],\n",
       "       [ 2.28036244,  2.86699026],\n",
       "       [ 7.42343694,  4.69652288],\n",
       "       [ 5.745052  ,  3.5339898 ],\n",
       "       [ 9.17216862,  2.51110105],\n",
       "       [ 7.79278348,  3.42408894],\n",
       "       [ 7.93982082,  0.79163723]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFGxJREFUeJzt3X9s5Hed3/HnaxNXYOA21a1b0mxs94/o1EIooVagpEUR\nWyoSEqgq/ggyIPHPNDSqQnsSKlgCpZL/OKlCK4hE5BLKRcyBroRDJAon6JIr8EfCeZclmx+oSq/x\nJml68UFx2BrdbeDdP2Y2eI29Htvj/Y6/+3xIo5n5zGfn+8oq89rvfH/MN1WFJKldDjQdQJI0fJa7\nJLWQ5S5JLWS5S1ILWe6S1EKWuyS1kOUuSS1kuUtSC1nuktRClze14EOHDtX09HRTi5ekfen48eN/\nVVUTW81rrNynp6dZXFxsavGStC8lWRpknptlJKmFLHdJaiHLXZJayHKXpBay3CWphSx3SWohy12S\nWshyl7Q3ul2YnoYDB3r33W7TiS4plrsA6J7qMn10mgN3HWD66DTdU34QtQvdLnQ6sLQEVb37TseC\nv4gsd9E91aXzQIellSWKYmllic4DHQteOzc3B6ur54+trvbGdVFY7mLu2ByrZ8//IK6eXWXumB9E\n7dDp09sb19BZ7uL0ysYfuM3GpS1NTm5vXENnuYvJgxt/4DYbl7Y0Pw/j4+ePjY/3xnVRWO5i/sg8\n42PnfxDHx8aZP+IHUTs0OwsLCzA1BUnvfmGhN66LorGf/NXomL2294GbOzbH6ZXTTB6cZP7I/Cvj\n0o7MzlrmDUpVNbLgmZmZ8vfcJWl7khyvqpmt5rlZRpJaaOByT3JZkh8leXCD125MspLkZP/2qeHG\nlCRtx3a2ud8JPAX8ziavf7+qbtl9JEnSbg205p7kMPAe4At7G0eSNAyDbpY5Cnwc+PUF5rw9yWNJ\nvpXkDRtNSNJJsphkcXl5ebtZJUkD2rLck9wCvFhVxy8w7QQwWVVvAj4HfGOjSVW1UFUzVTUzMTGx\no8CSpK0NsuZ+A/DeJM8AXwXemeTLaydU1UtVdab/+CFgLMmhYYeVJA1my3Kvqk9U1eGqmgZuA75b\nVR9cOyfJ65Ok//j6/vv+dA/ySpIGsOMzVJPcDlBV9wDvBz6a5GXgl8Bt1dTZUZIkz1CVpP3EM1Ql\n6RJmuUtSC1nuktRClrsktZDlLkktZLlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EKWuyS1kOUu\nSS1kuUtSC1nuktRCA5d7ksuS/CjJgxu8liSfTfJ0/yLZbxluTEnSdmxnzf1O4KlNXrsJuKZ/6wCf\n32UuSdIuDFTuSQ4D7wG+sMmU9wH3Vc8jwBVJrhxSRknSNg265n4U+Djw601evwp4ds3z5/pjkqQG\nbFnuSW4BXqyq47tdWJJOksUki8vLy7t9O0nSJgZZc78BeG+SZ4CvAu9M8uV1c54Hrl7z/HB/7DxV\ntVBVM1U1MzExscPIkqStbFnuVfWJqjpcVdPAbcB3q+qD66Z9E/hw/6iZtwErVfXC8ONKkgZx+U7/\nYJLbAarqHuAh4GbgaWAV+MhQ0kmSdmRb5V5Vfwb8Wf/xPWvGC7hjmMEkSTvnGaqS1EKWuyS1kOUu\nSS1kuUtSC1nuktRClrsktZDlLkktZLlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EKWuyS1kOUu\nSS1kuUt7oduF6Wk4cKB33+02nUiXmEEukP2qJD9M8uMkTyS5a4M5NyZZSXKyf/vU3sSV9oFuFzod\nWFqCqt59p2PB66IaZM39r4F3VtU/At4MvLt/ndT1vl9Vb+7f/uNQU0r7ydwcrK6eP7a62huXLpIt\nL7PXv4Temf7Tsf6t9jKUtK+dPr29cWkPDLTNPcllSU4CLwLfqapHN5j29iSPJflWkjcMNaW0n0xO\nbm9c2gMDlXtV/aqq3gwcBq5P8sZ1U04Ak1X1JuBzwDc2ep8knSSLSRaXl5d3k1saXfPzMD5+/tj4\neG9cg3GH9K5t62iZqvo58DDw7nXjL1XVmf7jh4CxJIc2+PMLVTVTVTMTExO7iC2NsNlZWFiAqSlI\nevcLC71xbc0d0kOR3ib1C0xIJoCzVfXzJK8Gvg38QVU9uGbO64G/rKpKcj3wNWCqLvDmMzMztbi4\nOJT/CEktMj3dK/T1pqbgmWcudpqRk+R4Vc1sNW+QNfcrgYeTPAb8Ob1t7g8muT3J7f057wceT/Jj\n4LPAbRcq9t3onuoyfXSaA3cdYProNN1T/msutYo7pIdikKNlHgOu22D8njWP7wbuHm6039Y91aXz\nQIfVs73DzJZWlug80AFg9lq/8kqtMDm58Zq7O6S3ZV+doTp3bO6VYj9n9ewqc8c8flhqDXdID8W+\nKvfTKxt/LdtsXNI+5A7podhys8womTw4ydLKb39dmzzo1zWpVWZnLfNd2ldr7vNH5hkfO//r2vjY\nOPNH/LomSWvtq3KfvXaWhVsXmDo4RQhTB6dYuHXBnamStM6Wx7nvFY9zl6TtG+Zx7pKkfcZyl6QW\nstwlqYUsd0lqIctdklrIcpekFrLcJamFLHdJaiHLXZJayHKXpBbastyTvCrJD5P8OMkTSe7aYE6S\nfDbJ00keS/KWvYkrSRrEID/5+9fAO6vqTJIx4AdJvlVVj6yZcxNwTf/2VuDz/XtJUgO2XHOvnjP9\np2P92/pfG3sfcF9/7iPAFUmuHG5USdKgBtrmnuSyJCeBF+ldIPvRdVOuAp5d8/y5/tj69+kkWUyy\nuLy8vNPMkqQtDFTuVfWrqnozcBi4Pskbd7KwqlqoqpmqmpmYmNjJW0iSBrCto2Wq6ufAw8C71730\nPHD1mueH+2OSpAYMcrTMRJIr+o9fDbwL+Mm6ad8EPtw/auZtwEpVvTD0tJKkgQyy5n4l8HCSx4A/\np7fN/cEktye5vT/nIeAvgKeB/wz8mz1JO4K6p7pMH53mwF0HmD46TfdUt+lIkrT1oZBV9Rhw3Qbj\n96x5XMAdw402+rqnunQe6LB6dhWApZUlOg90ALyuq6RGeYbqLswdm3ul2M9ZPbvK3LG5hhJJUo/l\nvgunV05va1ySLhbLfRcmD05ua1ySLhbLfRfmj8wzPjZ+3tj42DjzR+YbSiRJPZb7LsxeO8vCrQtM\nHZwihKmDUyzcuuDOVEmNS+9Al4tvZmamFhcXG1m2JO1XSY5X1cxW81xzl6QWstwlqYUsd0lqIctd\nklrIcpekFrLcJamFLHdJaiHLXZJayHKXpBay3CWphQa5zN7VSR5O8mSSJ5LcucGcG5OsJDnZv31q\nb+JK0j7V7cL0NBw40Lvv7u1V27a8EhPwMvD7VXUiyeuA40m+U1VPrpv3/aq6ZfgRJWmf63ah04HV\n/sV9lpZ6zwFm9+aHBrdcc6+qF6rqRP/xL4CngKv2JI0ktdHc3G+K/ZzV1d74HtnWNvck0/Sup/ro\nBi+/PcljSb6V5A2b/PlOksUki8vLy9sOK0n70ulNrs622fgQDFzuSV4L3A98rKpeWvfyCWCyqt4E\nfA74xkbvUVULVTVTVTMTExM7zSxJ+8vkJldn22x8CAYq9yRj9Iq9W1VfX/96Vb1UVWf6jx8CxpIc\nGmpSSdqv5udh/PyrtjE+3hvfI4McLRPgXuCpqvrMJnNe359Hkuv77/vTYQaVpH1rdhYWFmBqCpLe\n/cLCnu1MhcGOlrkB+BBwKsnJ/tgngUmAqroHeD/w0SQvA78EbqumLvEkSaNodnZPy3y9Lcu9qn4A\nZIs5dwN3DyuUJGl3PEP1EtI91WX66DQH7jrA9NFpuqf29iQKSc0ZZLOMWqB7qkvngQ6rZ3vH2i6t\nLNF5oHcSxey1F++roqSLwzX3S8TcsblXiv2c1bOrzB3bu5MoJDXHcr9EnF7Z+GSJzcYl7W+W+yVi\n8uDGJ0tsNi5pf7PcLxHzR+YZHzv/JIrxsXHmj+zdSRSSmmO5XyJmr51l4dYFpg5OEcLUwSkWbl1w\nZ6rUUmnqXKOZmZlaXFxsZNmStF8lOV5VM1vNc81dklrIcpekFrLcJamFLHdJaiHLXZJayHKXpBay\n3CWphQa5EtPVSR5O8mSSJ5LcucGcJPlskqf7F8l+y97ElSQNYpCf/H0Z+P2qOpHkdcDxJN+pqifX\nzLkJuKZ/eyvw+f69JKkBW665V9ULVXWi//gXwFPAVeumvQ+4r3oeAa5IcuXQ00qSBrKtbe5JpoHr\ngEfXvXQV8Oya58/x2/8ASJIukoHLPclrgfuBj1XVSztZWJJOksUki8vLyzt5C0nSAAYq9yRj9Iq9\nW1Vf32DK88DVa54f7o+dp6oWqmqmqmYmJiZ2kleSNIBBjpYJcC/wVFV9ZpNp3wQ+3D9q5m3ASlW9\nMMSckqRtGORomRuADwGnkpzsj30SmASoqnuAh4CbgaeBVeAjw48qSRrUluVeVT8AssWcAu4YVihJ\n0u54hqoktZDlLkktZLlLUgtZ7vtc91SX6aPTHLjrANNHp+me6jYdSdIIGORoGY2o7qkunQc6rJ5d\nBWBpZYnOAx0AZq+dbTKapIa55r6PzR2be6XYz1k9u8rcsbmGEkkaFZb7PnZ65fS2xiVdOiz3fWzy\n4OS2xiVdOiz3fWz+yDzjY+PnjY2PjTN/ZL6hRJJGheW+j81eO8vCrQtMHZwihKmDUyzcuuDOVEmk\n98sBF9/MzEwtLi42smxJ2q+SHK+qma3mueYuSS1kuUtSC1nuktRClrsktZDlLkktNMhl9r6Y5MUk\nj2/y+o1JVpKc7N8+NfyYkqTtGOSHw74E3A3cd4E536+qW4aSSJK0a1uuuVfV94CfXYQskqQhGdY2\n97cneSzJt5K8YUjvKUnaoWH8nvsJYLKqziS5GfgGcM1GE5N0gA7A5KQ/biVJe2XXa+5V9VJVnek/\nfggYS3Jok7kLVTVTVTMTExO7XbQkaRO7Lvckr0+S/uPr++/5092+ryRp57bcLJPkK8CNwKEkzwGf\nBsYAquoe4P3AR5O8DPwSuK2a+jUySRIwQLlX1Qe2eP1ueodKSpJGhGeoSlILWe6S1EKWuyS1kOUu\nSS1kuUtSC1nuktRClrsktZDlLkktZLlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EKWuyS1kOUu\nSS20Zbkn+WKSF5M8vsnrSfLZJE8neSzJW4YfU5K0HYOsuX8JePcFXr8JuKZ/6wCf330sSdJubFnu\nVfU94GcXmPI+4L7qeQS4IsmVwwooSdq+YWxzvwp4ds3z5/pjvyVJJ8liksXl5eUhLFqStJGLukO1\nqhaqaqaqZiYmJi7moiXpkjKMcn8euHrN88P9MUlSQ4ZR7t8EPtw/auZtwEpVvTCE95Uk7dDlW01I\n8hXgRuBQkueATwNjAFV1D/AQcDPwNLAKfGSvwkqSBrNluVfVB7Z4vYA7hpZIkrRrnqEqSS1kuUtS\nC1nukvaHbhemp+HAgd59t9t0opG25TZ3SWpctwudDqyu9p4vLfWeA8zONpdrhLnmLmn0zc39ptjP\nWV3tjWtDlruk0Xf69PbGZblL2gcmJ7c3Lstd0j4wPw/j4+ePjY/3xrUhy13S6JudhYUFmJqCpHe/\nsODO1AvwaBlJ+8PsrGW+Da65S1ILWe6S1EKWuyS1kOUuSS1kuUtSC1nuktRClrsktVB6F1JqYMHJ\nMrAEHAL+qpEQWzPbzoxqtlHNBWbbqVHNtpe5pqpqYqtJjZX7KwGSxaqaaTTEJsy2M6OabVRzgdl2\nalSzjUIuN8tIUgtZ7pLUQqNQ7gtNB7gAs+3MqGYb1Vxgtp0a1WyN52p8m7skafhGYc1dkjRkjZV7\nki8meTHJ401l2EySq5M8nOTJJE8kubPpTABJXpXkh0l+3M91V9OZ1ktyWZIfJXmw6SxrJXkmyakk\nJ5MsNp1nrSRXJPlakp8keSrJPxmBTL/X/7s6d3spyceaznVOkn/X/ww8nuQrSV7VdKZzktzZz/VE\nk39nTR7n/g7gDHBfVb2xkRCbSHIlcGVVnUjyOuA48C+r6smGcwV4TVWdSTIG/AC4s6oeaTLXWkn+\nPTAD/E5V3dJ0nnOSPAPMVNXIHROd5A+B71fVF5L8LWC8qn7edK5zklwGPA+8taqWRiDPVfT+3/+H\nVfXLJH8MPFRVX2o2GSR5I/BV4Hrgb4A/BW6vqqcvdpbG1tyr6nvAz5pa/oVU1QtVdaL/+BfAU8BV\nzaaC6jnTfzrWv43MTpMkh4H3AF9oOst+keQg8A7gXoCq+ptRKva+I8D/HIViX+Ny4NVJLgfGgf/d\ncJ5z/gHwaFWtVtXLwH8H/lUTQdzmvoUk08B1wKPNJunpb/Y4CbwIfKeqRiJX31Hg48Cvmw6ygQL+\nW5LjSTpNh1nj7wPLwH/pb876QpLXNB1qnduArzQd4pyqeh74T8Bp4AVgpaq+3WyqVzwO/LMkv5tk\nHLgZuLqJIJb7BSR5LXA/8LGqeqnpPABV9auqejNwGLi+/zWwcUluAV6squNNZ9nEP+3/vd0E3NHf\nLDgKLgfeAny+qq4D/h/wH5qN9Bv9zUTvBf5r01nOSfK3gffR+4fx7wGvSfLBZlP1VNVTwB8A36a3\nSeYk8Ksmsljum+hv074f6FbV15vOs17/q/vDwLubztJ3A/De/rbtrwLvTPLlZiP9Rn9tj6p6EfgT\nettER8FzwHNrvoF9jV7Zj4qbgBNV9ZdNB1njnwP/q6qWq+os8HXg7Q1nekVV3VtV/7iq3gH8X+B/\nNJHDct9Af8flvcBTVfWZpvOck2QiyRX9x68G3gX8pNlUPVX1iao6XFXT9L7Gf7eqRmJtKslr+jvG\n6W/y+Bf0vj43rqr+D/Bskt/rDx0BGt1xv84HGKFNMn2ngbclGe9/Vo/Q2y82EpL8nf79JL3t7X/U\nRI7Lm1goQJKvADcCh5I8B3y6qu5tKs86NwAfAk71t28DfLKqHmowE8CVwB/2j144APxxVY3UIYcj\n6u8Cf9LrAS4H/qiq/rTZSOf5t0C3vwnkL4CPNJwHeOUfwncB/7rpLGtV1aNJvgacAF4GfsQInBG6\nxv1Jfhc4C9zR1A5yz1CVpBZys4wktZDlLkktZLlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EL/\nH4mgOoxccwX2AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10c2d6978>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(X_train[y_train==0,0], X_train[y_train==0,1], color='g')\n",
    "plt.scatter(X_train[y_train==1,0], X_train[y_train==1,1], color='r')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "预测："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFHZJREFUeJzt3X9s5Hed3/HnaxNXYOA2p1u3pNnY0z/Q6QqhgVqBkhZF\nbKkIJFBV/BFkQOIfNzSqQnsSKlgCpZL/OKlCK0AimhLKRcyBrsAhEoUTdMkV+CPhvMuSzQ9Updd4\nkzS9+KBs2BrdbeDdP2Y2eH32emyP9zv+7vMhjWbmM5+deWWVee13PvP9zjdVhSSpXQ40HUCSNHqW\nuyS1kOUuSS1kuUtSC1nuktRClrsktZDlLkktZLlLUgtZ7pLUQlc29cKHDh2qTqfT1MtL0r50/Pjx\nv6qqqa3mNVbunU6HpaWlpl5ekvalJMvDzHNZRpJayHKXpBay3CWphSx3SWohy12SWshyl6QWstwl\nqYUsd0l7o9eDTgcOHOhf93pNJ7qsWO4CoHeqR+dohwN3HaBztEPvlG9E7UKvB/PzsLwMVf3r+XkL\n/hKy3EXvVI/5++ZZPrNMUSyfWWb+vnkLXju3sACrqxeOra72x3VJWO5i4dgCq+cufCOunltl4Zhv\nRO3Q6dPbG9fIWe7i9JmN33CbjUtbmp7e3rhGznIX0wc3fsNtNi5taXERJicvHJuc7I/rkrDcxeKR\nRSYnLnwjTk5MsnjEN6J2aG4Oul2YmYGkf93t9sd1STT2k78aH3PX9d9wC8cWOH3mNNMHp1k8svjS\nuLQjc3OWeYNSVY288OzsbPl77pK0PUmOV9XsVvNclpGkFhq63JNckeRHSe7f4LGbkpxJcnJw+cRo\nY0qStmM7a+53Ak8Av7XJ49+vqlt2H0mStFtDbbknOQy8C/j83saRJI3CsMsyR4GPAr++yJy3JHkk\nybeSvHajCUnmkywlWVpZWdluVknSkLYs9yS3AM9X1fGLTDsBTFfV64HPAN/YaFJVdatqtqpmp6am\ndhRYkrS1YbbcbwTeneQp4CvA25J8ae2Eqnqhqs4Obj8ATCQ5NOqwkqThbFnuVfWxqjpcVR3gNuC7\nVfX+tXOSvDpJBrdvGDzvT/cgryRpCDs+QjXJ7QBVdTfwXuDDSV4EfgncVk0dHSVJ8ghVSdpPPEJV\nki5jlrsktZDlLkktZLlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EKWuyS1kOUuSS1kuUtSC1nu\nktRClrsktZDlLkktNHS5J7kiyY+S3L/BY0ny6SRPDk6S/cbRxpQkbcd2ttzvBJ7Y5LGbgdcMLvPA\n53aZS5K0C0OVe5LDwLuAz28y5T3AvdX3EHBVkqtHlFGStE3DbrkfBT4K/HqTx68Bnl5z/5nBmCSp\nAVuWe5JbgOer6vhuXyzJfJKlJEsrKyu7fTpJ0iaG2XK/EXh3kqeArwBvS/KldXOeBa5dc//wYOwC\nVdWtqtmqmp2amtphZEnSVrYs96r6WFUdrqoOcBvw3ap6/7pp3wQ+ONhr5s3Amap6bvRxJUnDuHKn\nfzDJ7QBVdTfwAPBO4ElgFfjQSNJJknZkW+VeVX8G/Nng9t1rxgu4Y5TBJEk75xGqktRClrsktZDl\nLkktZLlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EKWuyS1kOUuSS1kuUtSC1nuktRClrsktZDl\nLkktZLlLe6HXg04HDhzoX/d6TSfSZWaYE2S/LMkPk/w4yWNJ7tpgzk1JziQ5Obh8Ym/iSvtArwfz\n87C8DFX96/l5C16X1DBb7n8NvK2q/hFwPfCOwXlS1/t+VV0/uPzHkaaU9pOFBVhdvXBsdbU/Ll0i\nW55mb3AKvbODuxODS+1lKGlfO316e+PSHhhqzT3JFUlOAs8D36mqhzeY9pYkjyT5VpLXjjSltJ9M\nT29vXNoDQ5V7Vf2qqq4HDgM3JHnduikngOmqej3wGeAbGz1PkvkkS0mWVlZWdpNbGl+LizA5eeHY\n5GR/XMPxC+ld29beMlX1c+BB4B3rxl+oqrOD2w8AE0kObfDnu1U1W1WzU1NTu4gtjbG5Oeh2YWYG\nkv51t9sf19b8Qnok0l9Sv8iEZAo4V1U/T/Jy4NvAH1TV/WvmvBr4y6qqJDcAXwVm6iJPPjs7W0tL\nSyP5j5DUIp1Ov9DXm5mBp5661GnGTpLjVTW71bxhttyvBh5M8gjw5/TX3O9PcnuS2wdz3gs8muTH\nwKeB2y5W7LvRO9Wjc7TDgbsO0DnaoXfKf82lVtnmF9Ku4Gxsyy33vbKTLffeqR7z982zeu43u5lN\nTkzSvbXL3HV+5JVaYRtb7udXcNbueTo52e5VsFFuuY+NhWMLFxQ7wOq5VRaOuf+w1Brb+ELaQwo2\nt6/K/fSZjT+WbTYuaR/axhfSHlKwuX1V7tMHN95PeLNxSfvU3Fx/CebXv+5fb7LG4iEFm9tX5b54\nZJHJiQs/rk1OTLJ4xP2HpcuRhxRsbl+V+9x1c3Rv7TJzcIYQZg7O+GWqdBnzkILN7au9ZSTpctfK\nvWUkScOx3CWphSx3SWohy12SWshyl6QWstwlqYUsd0lqIctdklrIcpekFrLcJamFtiz3JC9L8sMk\nP07yWJK7NpiTJJ9O8mSSR5K8cW/iSpKGceUQc/4aeFtVnU0yAfwgybeq6qE1c24GXjO4vAn43OBa\nktSALbfcq+/s4O7E4LL+18beA9w7mPsQcFWSq0cbVZI0rKHW3JNckeQk8Dz9E2Q/vG7KNcDTa+4/\nMxhb/zzzSZaSLK2srOw0syRpC0OVe1X9qqquBw4DNyR53U5erKq6VTVbVbNTU1M7eQpJ0hC2tbdM\nVf0ceBB4x7qHngWuXXP/8GBMktSAYfaWmUpy1eD2y4G3Az9ZN+2bwAcHe828GThTVc+NPK0kaSjD\nbLlfDTyY5BHgz+mvud+f5PYktw/mPAD8BfAk8J+Bf7MnacdQ71SPztEOB+46QOdoh96pXtORJGnr\nXSGr6hHgDRuM373mdgF3jDba+Oud6jF/3zyr51YBWD6zzPx98wCe11VSozxCdRcWji28VOznrZ5b\nZeHYQkOJJKnPct+F02dOb2tcki4Vy30Xpg9Ob2tcki4Vy30XFo8sMjkxecHY5MQki0cWG0okSX2W\n+y7MXTdH99YuMwdnCGHm4AzdW7t+mSqpcenv6HLpzc7O1tLSUiOvLUn7VZLjVTW71Ty33CWphSx3\nSWohy12SWshyl6QWstwlqYUsd0lqIctdklrIcpekFrLcJamFLHdJaqFhTrN3bZIHkzye5LEkd24w\n56YkZ5KcHFw+sTdxJWmf6vWg04EDB/rXvb09a9uWZ2ICXgR+v6pOJHkVcDzJd6rq8XXzvl9Vt4w+\noiTtc70ezM/D6uDkPsvL/fsAc3vzQ4NbbrlX1XNVdWJw+xfAE8A1e5JGktpoYeE3xX7e6mp/fI9s\na809SYf++VQf3uDhtyR5JMm3krx2kz8/n2QpydLKysq2w0rSvnR6k7OzbTY+AkOXe5JXAl8DPlJV\nL6x7+AQwXVWvBz4DfGOj56iqblXNVtXs1NTUTjNL0v4yvcnZ2TYbH4Ghyj3JBP1i71XV19c/XlUv\nVNXZwe0HgIkkh0aaVJL2q8VFmLzwrG1MTvbH98gwe8sEuAd4oqo+tcmcVw/mkeSGwfP+dJRBJWnf\nmpuDbhdmZiDpX3e7e/ZlKgy3t8yNwAeAU0lODsY+DkwDVNXdwHuBDyd5EfglcFs1dYonSRpHc3N7\nWubrbVnuVfUDIFvM+Szw2VGFkiTtjkeoXkZ6p3p0jnY4cNcBOkc79E7t7UEUkpozzLKMWqB3qsf8\nffOsnuvva7t8Zpn5+/oHUcxdd+k+Kkq6NNxyv0wsHFt4qdjPWz23ysKxvTuIQlJzLPfLxOkzGx8s\nsdm4pP3Ncr9MTB/c+GCJzcYl7W+W+2Vi8cgikxMXHkQxOTHJ4pG9O4hCUnMs98vE3HVzdG/tMnNw\nhhBmDs7QvbXrl6lSS6WpY41mZ2draWmpkdeWpP0qyfGqmt1qnlvuktRClrsktZDlLkktZLlLUgtZ\n7pLUQpa7JLWQ5S5JLTTMmZiuTfJgkseTPJbkzg3mJMmnkzw5OEn2G/cmriRpGMP85O+LwO9X1Ykk\nrwKOJ/lOVT2+Zs7NwGsGlzcBnxtcS5IasOWWe1U9V1UnBrd/ATwBXLNu2nuAe6vvIeCqJFePPK0k\naSjbWnNP0gHeADy87qFrgKfX3H+Gv/0PgCTpEhm63JO8Evga8JGqemEnL5ZkPslSkqWVlZWdPIUk\naQhDlXuSCfrF3quqr28w5Vng2jX3Dw/GLlBV3aqararZqampneSVJA1hmL1lAtwDPFFVn9pk2jeB\nDw72mnkzcKaqnhthTknSNgyzt8yNwAeAU0lODsY+DkwDVNXdwAPAO4EngVXgQ6OPKkka1pblXlU/\nALLFnALuGFUoSdLueISqJLWQ5S5JLWS5S1ILWe77XO9Uj87RDgfuOkDnaIfeqV7TkSSNgWH2ltGY\n6p3qMX/fPKvnVgFYPrPM/H3zAMxdN9dkNEkNc8t9H1s4tvBSsZ+3em6VhWMLDSWSNC4s933s9JnT\n2xqXdPmw3Pex6YPT2xqXdPmw3PexxSOLTE5MXjA2OTHJ4pHFhhJJGheW+z42d90c3Vu7zBycIYSZ\ngzN0b+36Zaok0v/lgEtvdna2lpaWGnltSdqvkhyvqtmt5rnlLkktZLlLUgtZ7pLUQpa7JLWQ5S5J\nLTTMafa+kOT5JI9u8vhNSc4kOTm4fGL0MSVJ2zHMD4d9EfgscO9F5ny/qm4ZSSJJ0q5tueVeVd8D\nfnYJskiSRmRUa+5vSfJIkm8lee2InlOStEOj+D33E8B0VZ1N8k7gG8BrNpqYZB6YB5ie9setJGmv\n7HrLvapeqKqzg9sPABNJDm0yt1tVs1U1OzU1tduXliRtYtflnuTVSTK4fcPgOX+62+eVJO3clssy\nSb4M3AQcSvIM8ElgAqCq7gbeC3w4yYvAL4HbqqlfI5MkAUOUe1W9b4vHP0t/V0lJ0pjwCFVJaiHL\nXZJayHKXpBay3CWphSx3SWohy12SWshyl6QWstwlqYUsd0lqIctdklrIcpekFrLcJamFLHdJaiHL\nXZJayHKXpBay3CWphbYs9yRfSPJ8kkc3eTxJPp3kySSPJHnj6GNKkrZjmC33LwLvuMjjNwOvGVzm\ngc/tPpYkaTe2LPeq+h7ws4tMeQ9wb/U9BFyV5OpRBZQkbd8o1tyvAZ5ec/+ZwdjfkmQ+yVKSpZWV\nlRG8tCRpI5f0C9Wq6lbVbFXNTk1NXcqXlqTLyijK/Vng2jX3Dw/GJEkNGUW5fxP44GCvmTcDZ6rq\nuRE8ryRph67cakKSLwM3AYeSPAN8EpgAqKq7gQeAdwJPAqvAh/YqrCRpOFuWe1W9b4vHC7hjZIkk\nSbvmEaqS1EKWuyS1kOUuaX/o9aDTgQMH+te9XtOJxtqWa+6S1LheD+bnYXW1f395uX8fYG6uuVxj\nzC13SeNvYeE3xX7e6mp/XBuy3CWNv9Ontzcuy13SPjA9vb1xWe6S9oHFRZicvHBscrI/rg1Z7pLG\n39wcdLswMwNJ/7rb9cvUi3BvGUn7w9ycZb4NbrlLUgtZ7pLUQpa7JLWQ5S5JLWS5S1ILWe6S1EKW\nuyS1UPonUmrghZMVYBk4BPxVIyG2ZradGdds45oLzLZT45ptL3PNVNXUVpMaK/eXAiRLVTXbaIhN\nmG1nxjXbuOYCs+3UuGYbh1wuy0hSC1nuktRC41Du3aYDXITZdmZcs41rLjDbTo1rtsZzNb7mLkka\nvXHYcpckjVhj5Z7kC0meT/JoUxk2k+TaJA8meTzJY0nubDoTQJKXJflhkh8Pct3VdKb1klyR5EdJ\n7m86y1pJnkpyKsnJJEtN51kryVVJvprkJ0meSPJPxiDT7w7+rs5fXkjykaZznZfk3w3eA48m+XKS\nlzWd6bwkdw5yPdbk31mT+7m/FTgL3FtVr2skxCaSXA1cXVUnkrwKOA78y6p6vOFcAV5RVWeTTAA/\nAO6sqoeazLVWkn8PzAK/VVW3NJ3nvCRPAbNVNXb7RCf5Q+D7VfX5JH8HmKyqnzed67wkVwDPAm+q\nquUxyHMN/f/3/2FV/TLJHwMPVNUXm00GSV4HfAW4Afgb4E+B26vqyUudpbEt96r6HvCzpl7/Yqrq\nuao6Mbj9C+AJ4JpmU0H1nR3cnRhcxuZLkySHgXcBn286y36R5CDwVuAegKr6m3Eq9oEjwP8ch2Jf\n40rg5UmuBCaB/91wnvN+D3i4qlar6kXgvwP/qokgrrlvIUkHeAPwcLNJ+gbLHieB54HvVNVY5Bo4\nCnwU+HXTQTZQwH9LcjzJfNNh1vgHwArwXwbLWZ9P8oqmQ61zG/DlpkOcV1XPAv8JOA08B5ypqm83\nm+oljwL/LMnvJJkE3glc20QQy/0ikrwS+Brwkap6oek8AFX1q6q6HjgM3DD4GNi4JLcAz1fV8aaz\nbOKfDv7ebgbuGCwLjoMrgTcCn6uqNwD/D/gPzUb6jcEy0buB/9p0lvOS/DbwHvr/MP594BVJ3t9s\nqr6qegL4A+Db9JdkTgK/aiKL5b6JwZr214BeVX296TzrDT66Pwi8o+ksAzcC7x6sbX8FeFuSLzUb\n6TcGW3tU1fPAn9BfEx0HzwDPrPkE9lX6ZT8ubgZOVNVfNh1kjX8O/K+qWqmqc8DXgbc0nOklVXVP\nVf3jqnor8H+B/9FEDst9A4MvLu8BnqiqTzWd57wkU0muGtx+OfB24CfNpuqrqo9V1eGq6tD/GP/d\nqhqLrakkrxh8Mc5gyeNf0P/43Liq+j/A00l+dzB0BGj0i/t13scYLckMnAbenGRy8F49Qv97sbGQ\n5O8Orqfpr7f/URM5rmziRQGSfBm4CTiU5Bngk1V1T1N51rkR+ABwarC+DfDxqnqgwUwAVwN/ONh7\n4QDwx1U1Vrscjqm/B/xJvwe4EvijqvrTZiNd4N8CvcESyF8AH2o4D/DSP4RvB/5101nWqqqHk3wV\nOAG8CPyIMTgidI2vJfkd4BxwR1NfkHuEqiS1kMsyktRClrsktZDlLkktZLlLUgtZ7pLUQpa7JLWQ\n5S5JLWS5S1IL/X8hFFUrJQgxUQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10c2d6908>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = np.array([8.093607318, 3.365731514])\n",
    "\n",
    "plt.scatter(X_train[y_train==0,0], X_train[y_train==0,1], color='g')\n",
    "plt.scatter(X_train[y_train==1,0], X_train[y_train==1,1], color='r')\n",
    "plt.scatter(x[0], x[1], color='b')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### kNN的过程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "distances = []\n",
    "for x_train in X_train:\n",
    "    d = sqrt(np.sum((x_train - x)**2))\n",
    "    distances.append(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4.812566907609877,\n",
       " 5.229270827235305,\n",
       " 6.749798999160064,\n",
       " 4.6986266144110695,\n",
       " 5.83460014556857,\n",
       " 1.4900114024329525,\n",
       " 2.354574897431513,\n",
       " 1.3761132675144652,\n",
       " 0.3064319992975,\n",
       " 2.5786840957478887]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "distances = [sqrt(np.sum((x_train - x)**2))\n",
    "             for x_train in X_train]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4.812566907609877,\n",
       " 5.229270827235305,\n",
       " 6.749798999160064,\n",
       " 4.6986266144110695,\n",
       " 5.83460014556857,\n",
       " 1.4900114024329525,\n",
       " 2.354574897431513,\n",
       " 1.3761132675144652,\n",
       " 0.3064319992975,\n",
       " 2.5786840957478887]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([8, 7, 5, 6, 9, 3, 0, 1, 4, 2])"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.argsort(distances)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nearest = np.argsort(distances)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "k = 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "topK_y = [y_train[neighbor] for neighbor in nearest[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 1, 1, 0]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "topK_y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "votes = Counter(topK_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({0: 1, 1: 5})"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 5)]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "votes.most_common(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "predict_y = votes.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predict_y"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
